package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author zhangjy
 * @description 二叉树的前序遍历
 * @date 2025/3/4 21:59
 */
public class PreorderTraversal_144 {

    public static void main(String[] args) {
        PreorderTraversal_144 preorderTraversal144 = new PreorderTraversal_144();

    }

    /**
     * 为什么说迭代法中，前序遍历的遍历节点顺序与处理节点的顺序一致，而中序、后序两者顺序不同？
     * <p>
     * 因为，入栈是在遍历节点，而出栈是在处理节点；但是出栈并不表示一定处理根节点，也可以处理右节点。
     * <p>
     * 对于前序遍历，
     */

    /**
     * 栈：按照根左右顺序遍历，入栈时记录节点值val
     */
    public List<Integer> preorderTraversal4(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Stack<TreeNode> st = new Stack<>();
        TreeNode node = root;
        while (!st.isEmpty() || node != null) {
            while (node != null) {
                // 根（入栈并记录）
                st.push(node);
                res.add(node.val);
                // 左（更新为左孩子，保持先序遍历根左右的顺序）
                node = node.left;
            }
            // 右（当前栈顶元素的左子树为空，需要将其出栈，然后处理其右子树，即，遍历到左叶子节点，弹出栈里的节点开始处理右孩子）
            node = st.pop();
            node = node.right;
        }
        return res;
    }

    /**
     * 参照dmsxl解法：遍历、处理节点的顺序一致，出栈时记录
     */
    public List<Integer> preorderTraversal3(TreeNode root) {
        Stack<TreeNode> st = new Stack<>();
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        st.push(root);
        while (!st.isEmpty()) {
            // 出栈，记录节点值val
            TreeNode node = st.pop();
            /// 空节点不处理
            if (node == null) continue;
            res.add(node.val);

            // 并按顺序入栈右—>左，从而确保出栈是中左右顺序
            st.push(node.right);
            st.push(node.left);
        }

        return res;
    }

    /**
     * 栈实现（迭代法）：dmsxl解法；
     * <p>
     * 遍历节点、处理节点；
     * <p>
     * 先序的迭代实现，遍历的顺序刚好和处理的顺序相同，所以比较简单。
     */
    public List<Integer> preorderTraversal2(TreeNode root) {
        Stack<TreeNode> nodes = new Stack<>();
        List<Integer> vals = new ArrayList<>();

        if (root == null) return vals;

        nodes.push(root);
        while (!nodes.isEmpty()) {
            // 根左右，先处理根，再处理左右子节点；
            // 弹出栈后记录：弹出是因为要处理给该节点，需要把其val记录到res
            TreeNode node = nodes.pop();
            vals.add(node.val);

            // 非空入栈，先右后左，保证出栈为根左右顺序
            if (node.right != null) nodes.push(node.right);
            if (node.left != null) nodes.push(node.left);
        }

        return vals;
    }

    // 递归
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root, res);
        return res;

    }

    public void preorder(TreeNode node, List<Integer> preorderVals) {
        // 目的：前序遍历，并按顺序记录节点值

        // 1.返回值、入参：
        // 无返回值；入参：node、记录前序遍历顺序节点值的集合vals；
        // 2.递归终止条件；
        if (node == null) return;

        // 3.单层递归逻辑：根—>左—>右的顺序，把节点值加入list
        // 先记录每一层根节点的val，再按顺序遍历本层（左—>右）
        preorderVals.add(node.val);
        preorder(node.left, preorderVals);
        preorder(node.right, preorderVals);
    }

}
